package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/27 11:44
 * 链表中环的入口结点
 * 算法：链表 + 快慢指针
 * 假设环入口节点为 B，之前的路径为 A，相遇的节点为 C(快指针走两步，所以在第二圈的时候肯定能追上慢指针)
 * 慢指针走的距离为 X(A - B) + Y(B - C)
 * 快指针走的距离为慢指针的两倍, 所以走的距离为 2(X + Y), 路径为 A - B - C - B - C
 * 所以 (C - B) = X(A - B)
 * 先找到 C 节点，然后再让快指针移到头节点，快慢指针每次只走一步，当相遇的时候，就是环入口
 */
public class NC3 {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead, fast = pHead;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        if (fast == null || fast.next == null) return null;
        fast = pHead;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

}
